#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/14
# @Author   :Changshu
# @File     :practice_112.py

# 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

from collections import deque


class TreeNode:
	def __init__(self,x):
		self.val=x
		self.left=None
		self.right=None
'''广度优先遍历
def hasPathSum(root: TreeNode, sum: int) -> bool:
	if not root:
		return False
	queue_node=deque([root])
	queue_sum=deque([root.val])

	while queue_node:
		p=queue_node.popleft()
		s=queue_sum.popleft()
		if not p.left and not p.right:
			if s == sum:
				return True
			continue
		if p.left:
			queue_node.append(p.left)
			queue_sum.append(p.left.val+s)
		if p.right:
			queue_node.append(p.right)
			queue_sum.append(p.right.val+s)
	return False
'''

'''深度优先遍历，采用递归'''
def hasPathSum(root: TreeNode, sum: int) -> bool:
	if not root:
		return False
	if not root.left and not root.right:
		return root.val==sum
	return hasPathSum(root.left,sum-root.val) or hasPathSum(root.right,sum-root.val)


if __name__ == '__main__':
	root=TreeNode(5)
	node2_1=TreeNode(4)
	node2_2=TreeNode(8)
	node3_1=TreeNode(11)
	node3_2=TreeNode(12)
	node3_3=TreeNode(4)
	node4_1=TreeNode(7)
	node4_2=TreeNode(2)
	node4_3=TreeNode(1)

	root.left=node2_1
	root.right=node2_2
	node2_1.left=node3_1
	node2_2.left=node3_2
	node2_2.right=node3_3
	node3_1.left=node4_1
	node3_1.right=node4_2
	node3_3.right=node4_3

	b=hasPathSum(root,22)
	print(b)